/*
题目：路径总和Ⅲ
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
https://leetcode.cn/problems/path-sum-iii
 */
public class PathSumⅢ {
    public int pathSum(TreeNode root, int targetSum) {
        //哈希表 + 前缀和
        Map<Integer, Integer> prefix = new HashMap<> (); // Key: 前缀和  Value：该前缀和的个数
        prefix.put(0, 1);  //像是设立一个头节点的路径
        return searchPath(root, prefix, 0, targetSum);
    }

    private int searchPath(TreeNode root, Map<Integer, Integer> prefix, int currSum, int targetSum) {
        if (root == null) {
            return 0;
        }
        currSum += root.val; //到当前节点的前缀和
        int ret = prefix.getOrDefault(currSum - targetSum, 0); //如果存在：i 节点前缀和 - j 节点前缀和 = targetSum， 说明这两个节点之间的路径和为targetSum
        prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1); //建立到这个根节点为止的路径前缀和

        ret += searchPath(root.left, prefix, currSum, targetSum);
        ret += searchPath(root.right, prefix, currSum, targetSum);

        prefix.put(currSum, prefix.get(currSum) - 1); //去掉到当前节点为止的路径前缀和
        return ret;
    }
}
